Pattern occurrence statistics and applications to the Ramsey theory of unavoidable patterns

摘要

As suggested by Currie, we apply the probabilistic method to problemsregarding pattern avoidance. Using techniques from analytic combinatorics, wecalculate asymptotic pattern occurrence statistics and use them in conjunctionwith the probabilistic method to establish new results about the Ramsey theoryof unavoidable patterns in the full word case (both nonabelian sense andabelian sense) and in the partial word case. Keywords: Combinatorics on words; Partial words; Unavoidable patterns;Abelian patterns; Probabilistic method; Analytic combinatorics; Ramsey theory.